\documentclass{ctexart}
 \usepackage{graphicx} 
 \usepackage{listings}
 \usepackage{color}
 
 \pagestyle{headings}
 
\title{Sorting设计思路和测试说明}
\author{谢飞扬 \\ 信息与计算科学 3210104010}
\date{\today}

\definecolor{green}{rgb}{0,0.7,0}
\definecolor{blue}{rgb}{0,0,0.8}
\definecolor{gray}{rgb}{0.95,0.95,0.95}
\definecolor{red}{rgb}{0.6,0,0}

\lstset{
        language=C++,
	basicstyle=\small\ttfamily,	
		keywordstyle=\color{blue}, 
		commentstyle=\color{green},   
		stringstyle=\rmfamily\slshape\color{red}, 
	backgroundcolor=\color{gray},     % 代码块背景颜色
	frame=leftline,						% 代码框形状
	framerule=12pt,
	rulecolor=\color{gray},      % 代码框颜色
	numbers=left,				% 左侧显示行号往左靠, 还可以为right ，或none，即不加行号
		numberstyle=\footnotesize\itshape,	% 行号的样式
		firstnumber=1,
		stepnumber=1,                  	% 若设置为2，则显示行号为1,3,5
		numbersep=5pt,               	% 行号与代码之间的间距
	keepspaces=true, 					
	showtabs=false,                 	% 在字符串中显示制表符
	tabsize=2,                     		% 默认缩进2个字符
	captionpos=b,                   	% 将标题位置设置为底部
	flexiblecolumns=true, 			%
	breaklines=true,                	% 设置自动断行
	breakatwhitespace=false,        	% 设置自动中断是否只发生在空格处
	breakautoindent=true,			%
	breakindent=1em, 			%
	title=\lstname,				%
	xleftmargin=1em,  xrightmargin=0em,     % 设定listing左右的空白
	aboveskip=1ex, belowskip=1ex,
	framextopmargin=0.5pt, framexbottommargin=0.5pt,
        abovecaptionskip=-2pt,belowcaptionskip=3pt,
	% 设定中文冲突，断行，列模式，数学环境输入，listing数字的样式
	extendedchars=false, columns=flexible, mathescape=true,
	texcl=true,
        fontadjust
}

\begin{document}
\maketitle
\section{项目设计思路}
\subsection{堆排和快排效率比较}
heapsort和quicksort的代码由课本提供。在设计有序度符合要求的数组时遇到了一些困难，最后打算通过随机交换的方法来生成有序度近似的数组。首先，助教在群里给出的有序度计算公式，是用数组的顺序数除以排序后的数组的顺序数计算的。排序后的数组顺序数很简单，为$n*(n-1)/2$，排序前的数组顺序数则用双循环计算。我先生成一个有序数组（或完全逆序数组），采用类似洗牌算法的方式，每次随机交换数组中的两个数，通过控制打乱的次数，来使有序度逼近作业要求。有序数组，最多通过随机打乱，把有序度降到50\%左右，因此通过打乱完全逆序数组来生成1\%和10\%有序的数组。然后再多次调用堆排和快排，比较排序效率。
\subsection{快排优化}
快排的优化大概分几方面，枢轴的选取、分割策略、小数组处理。枢轴选取，课本采用了三数中值法，我将其优化为五数中值法，进一步使枢轴接近中间数，使得数组的分割更加平均，减少了数组不平衡导致快排递归次数增多的可能性，从而提高了快排效率。分割策略方面，遍历并交换大小不符要求的数，以及小数组方面，在数组n＝10时调用插入排序，课本本身优化地很好，我目前还想不到更好的优化策略。
\section{测试说明}
\subsection{堆排和快排效率比较}
分别在各个有序度下，重复测试5次，每次堆排和快排处理相同的数组，数组大小为20000，记录每次排序的时间，下图为每次的输出结果。可以看到，随着有序度的增加，堆排和快排相比，快排的速度比堆排快一个数量级。另外，堆排和快排在不同有序度下从慢到快，先后是10％的有序度，1％有序度，90％有序度，99％有序度。出现这样的结果有两个主要原因，一是堆排在建堆的过程中会改变数据原有的相对顺序，可能降低有序度，导致堆排交换数据次数增加;二是堆排数据是跳跃着访问，cpu速度相对较慢。
\begin{figure}[htbp]
  \centering
  \begin{minipage}{6cm}
    \centering
    \includegraphics[width=6cm,height=5.5cm]  {pic/1.png}
  \caption{1\%有序度}
  \end{minipage}
  \begin{minipage}{6cm}
    \centering
    \includegraphics[width=6cm,height=5.5cm]  {pic/10.png}
  \caption{10\%有序度}
  \end{minipage}
  \begin{minipage}{6cm}
    \centering
    \includegraphics[width=6cm,height=5.5cm]  {pic/90.png}
  \caption{90\%有序度}
  \end{minipage}
  \begin{minipage}{6cm}
    \centering
    \includegraphics[width=6cm,height=5.5cm]  {pic/99.png}
  \caption{99\%有序度}
  \end{minipage}
\end{figure}

\subsection{快排优化}
经过五次测试，每次测试在90％有序度的条件下分别为快排和改进快排调用两次排序。将每次快排的平均值和优化快排的平均值相比较，从图中容易看出，此时优化的快排速度稍快，说明优化有效果。但在10％有序度情况下，优化快排无明显优势，说明高度逆序时，五取法和三取法取到的枢轴无较大差异，基本都比较均衡。
\begin{figure}[htbp]
  \centering
  \begin{minipage}{6cm}
    \centering
    \includegraphics[width=6cm]  {pic/yh90.png}
    \caption{90\%有序度}
  \end{minipage}
  \begin{minipage}{6cm}
    \centering
    \includegraphics[width=6cm]  {pic/yh10.png}
    \caption{10\%有序度}
  \end{minipage}
\end{figure}
\end{document}
